import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Solitudefire
 * Date: 2022-08-16
 * Time: 15:06
 */
public class TestDemo {
    /**
     * 求的是出现次数最多的单词
     *
     * @param words
     * @param k
     * @return
     */
    public static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        //1.统计每个单词出现的次数map
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            } else {
                int val = map.get(s);
                map.put(s, val + 1);
            }
        }
        //2.建立一个大小为k的小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });

        //3.遍历Map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                //说明堆中 已经放满了K个元素，需要看堆顶元素的数据和当前数据的大小关系
                Map.Entry<String, Integer> top = minHeap.peek();
                //判断频率是否相同，如果相同，比较单词的大小，如果单词小的入堆
                if (top.getValue().compareTo(entry.getValue()) == 0) {
                    if (top.getKey().compareTo(entry.getKey()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top  = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }

    public static void main(String[] args) {
        String[] worlds = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> ret = topKFrequent(worlds, 3);
        System.out.println(ret);
    }


//    public Node copyRandomList(Node head) {
//        Node cur = head;
//        HashMap<Node,Node> hashmap = new HashMap();
//        while(cur != null){
//            Node node = new Node(cur.val);
//            hashmap.put(cur,node);
//            cur = cur.next;
//        }
//        cur = head;
//        while(cur != null){
//            hashmap.get(cur).next = hashmap.get(cur.next);
//            hashmap.get(cur).random = hashmap.get(cur.random);
//            cur = cur.next;
//        }
//        return hashmap.get(head);
//    }

    public static int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> hashset = new HashSet();
        int count = 0;
        for (int i = 0; i < jewels.length(); i++) {
            hashset.add(jewels.charAt(i));
        }
        for (int i = 0; i < stones.length(); i++) {
            if (hashset.contains(stones.charAt(i))) {
                count++;
            }
        }
        return count;
    }

    public static void func(String strExce, String strActual) {
        HashSet<Character> set = new HashSet();
        HashSet<Character> broken = new HashSet();
        for (char x : strActual.toCharArray()) {
            set.add(x);
            if (x >= 65 && x <= 90) {
                set.add((char) (x + 32));
            }
            if (x >= 97 && x <= 122) {
                set.add((char) (x - 32));
            }
        }
        for (char x : strExce.toCharArray()) {
            if (!set.contains(x)) {
                if (!broken.contains(x)) {
                    broken.add(x);
                    if (x >= 65 && x <= 90) {
                        set.add((char) (x + 32));
                    }
                    if (x >= 97 && x <= 122) {
                        set.add((char) (x - 32));
                    }
                    if (x >= 97 && x <= 122) {
                        System.out.print((char) (x - 32));
                    } else {
                        System.out.print(x);
                    }
                }
            }
        }
    }

    public static void func1(String strExce, String strActual) {
        HashSet<Character> set = new HashSet<>();
        for (char ch : strActual.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        for (char ch : strExce.toUpperCase().toCharArray()) {
            if (!set.contains(ch)) {
                System.out.print(ch);
            }
        }
    }

    public static void main2(String[] args) {
        String strExce = null;
        String strActual = null;
        func(strExce, strActual);
    }

    public static void main1(String[] args) {
        String jew = "aA";
        String stones = "aAAbbbb";
        System.out.println(numJewelsInStones(jew, stones));
        System.out.println("========");
    }
}
